package Ep05_StackAndQueue._0239;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/4/14 19:25
 * 说明：Deque 双向队列
 */

// 先手动构建一个单调队列
class MyDeque {
    Deque<Integer> deque = new ArrayDeque<>();
    //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出，表示这个元素是因为滑动窗口的移动而被弹出的
    //同时判断队列当前是否为空
    void poll(int val){
        if (!deque.isEmpty() && val == deque.peek()){
            deque.pollFirst();
        }
    }

    //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
    //保证队列元素单调递减
    //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
    void add(int val){
        while (!deque.isEmpty() && val > deque.getLast()){
            deque.pollLast();
        }
        deque.add(val);
    }

    //队列队顶元素始终为最大值
    int peek(){
        return deque.peekFirst();
    }
}

class Best {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        int len = nums.length - k + 1;
        MyDeque myDeque = new MyDeque();
        int[] res = new int[len];
        int num = 0;

        for (int i = 0; i < k; i++) {
            myDeque.add(nums[i]);
        }
        res[num++] = myDeque.peek();
        for (int i = k; i < nums.length; i++){
            //滑动窗口移除最前面的元素
            myDeque.poll(nums[i-k]);
            //滑动窗口加入最后面的元素
            myDeque.add(nums[i]);
            res[num++] = myDeque.peek();
        }
        return res;
    }
}

